'''
https://leetcode.cn/problems/count-numbers-with-unique-digits/
'''

class Solution:

    # 0: 1
    # 1: 10
    # 2: 10 + 9*9
    # 3: 10 + 9*9 + 9*9*8
    # 4: 10 + 9*9 + 9*9*8 + 9*9*8*7
    # 5: 10 + 9*9 + 9*9*8 + 9*9*8*7 + 9*9*8*7*6
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        if n == 1:
            return 10
        res, cur = 10, 9
        for i in range(n - 1):
            cur *= 9 - i
            res += cur
        return res
